LCP array
After creating suffix array, record the length of the LCP (longest common prefix) of the adjacent string. O(N) by the Kasai method
A Fast Algorithm Using Suffix Arrays for the Subword Counting Problem" PDF. The LCP length of any two items matches the minimum LCP length between the two
This information can be used to speed up the binary search.
When query length M, naive O(MlogN) becomes O(M+logN)
---
This page is auto-translated from /nishio/LCP array. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.